Because of clock skew and related timing problems associated with the use of moderate-rate parallel data links for the routing of data having high aggregate bandwidths, high speed serial data links with clock recovery circuits are considered as alternatives to the moderate-bandwidth parallel data links. Several manufacturers produce multiplexer/transmitter chips that will accept data from parallel data lines and transform that data into a single high-speed data stream. These manufacturers also make receiver/demultiplexer chips which receive the high speed serial data and transform it back into parallel data. By using such devices, most of the hardware design for serial communication links is already done. However, to prevent the bit errors that occur when the clock recovery circuit loses synchronization, more than this hardware is needed to ensure synchronization between the recovered clock and the incoming serial data stream is maintained. Serial data communication links are known to have synchronization and related problems, and although there have been some solutions to these problems, all of the popular solutions still have problems that lead to bit errors.
A high speed serial data link may use some type of power driver and a metallic cable, such as coax or twinax to an electrical receiver, or some type of optical source and an optical fiber to a photonic receiver. In either case, the fundamental problem of clock distribution, described above, is encountered, i.e. synchronous clock signals cannot be distributed in parallel with the data with sufficient phase accuracy of the temporal placement of the clock edges, to prevent bit errors as the arriving data bits are inaccurately clocked into receiving registers at the receiver sub-system. The relatively short period of the data bits in the high-speed communication link operating at 1 gigabit per second or faster only exacerbates this clocking problem. Therefore, the receiver sub-system usually includes a clock recovery circuit which extracts a clock signal from the arriving data stream using a phase-locked loop rather than a clock signal distributed in parallel with the data. The recovered clock has bit edges whose phase with respect to the arriving serial data is very well defined, assuming that the phase of the data does not shift to any great degree. As a result, the recovered clock can be used to clock the arriving data into registers at the receiver sub-system. However, in order for the recovered clock to have sufficient phase accuracy to prevent bit errors, the phase lock loop must be provided with frequent logic 0 to logic 1 and logic 1 to logic 0 transitions within the serial data stream. The presence of these transitions allows the phase-locked loop to periodically correct for any accumulating phase errors in the recovered clock. Thus, to prevent phase inaccuracies in the recovered clock that lead to bit errors, it is desirable that frequent data transitions occur in the received data stream.
If a high-speed serial communication link is implemented using metallic cable, a second fundamental problem of high speed serial data links may also be encountered. The shield on a coaxial cable is typically tied to the signal ground plane of the printed circuit board from which the signal originated. If the shield is also tied to the signal ground plane of the receiver, ground loop problems, e.g. undesirable current flow and voltage drops, can develop if the ground planes on the two circuit boards develop a potential difference between them. In order to eliminate this ground loop problem, AC-coupling may be used at the receiver end, using one capacitor to connect the coaxial cable center wire to a input conductor at the receiver and another capacitor to connect the shield of the coaxial cable to a ground conductor of the receiver. As is well known, these capacitors provide low impedances for high-frequency signals such as the high speed data stream, but they also provide high impedances for the low frequency ground loop signals that might flow due to potential differences between the transmitter and receiver. However, in order for any AC-coupling to be used, the receiver system must guarantee a data stream that has an average density of logic 1's that is close to fifty percent, because a long-stream of logic 1's or logic 0's contains low-frequency signal components that will be filtered out and stored by the capacitors as DC levels, and the voltage on the output of the AC-coupled receiver will drift toward its bias point, which is usually the threshold of the decision circuit as well. As a result of this "DC wander" effect, the decision circuit will have difficulty differentiating between arriving logic 1's and arriving logic 0's, and the bit error rate on the serial communication link will increase if any noise is coupled into the link. In other words, there can be a long sequence of logic 1's in the data stream as long as it is followed by a long sequence of logic 0's such that the overall logic 1's density in a longer time window is still close to fifty percent. The noise sensitivity of a typical receiving circuit has been improving, and will probably continue to do so, such that it is now possible to have logic 1's densities in the serial link data streams that vary from the ideal fifty percent level. The use of a density of logic 1's may vary between k.sub.1 and k.sub.2, for 0&lt;k.sub.1 .ltoreq.k.sub.2 &lt;1, where the values of k.sub.1 and k.sub.2 are determined by many factors. Acceptable values for k.sub.1 and k.sub.2 are a function of the block size of the data, the bit rate on the high speed serial link and the data receiver circuit, i.e. the input RC time constant, the bias level, the threshold levels of the decision circuit, the amplitude of the noise signal and the desired bit error rate.
If the high-speed serial data link is implemented using optical fiber, then a third fundamental problem may be encountered. Laser driver circuits, laser sources, photo-detectors, and optical receiver circuits, e.g.; amplifiers and decision circuits, comprise the primary active components within a serial fiber link, and the operation of each of these components can vary quite extensively with temperature. A data stream with a long sequence of logic 1's, i.e.; laser source on, will often dissipate more power and produce much more heat in the active components than a long sequence of logic 0's, so the temperature of the components can vary with the bit patterns. As a result, the performance of the components can also vary with the bit patterns, resulting in bit pattern dependent pulse width distortion, pulse amplitude distortion and jitter. Because of these problems, a data stream that has a very high logic 1's density or a very low logic 1's density will experience higher bit error rates. Thus, bit streams with very high logic 1's densities or very low logic 1's densities should be avoided. This requirement coincides very well with the logic 1's density requirement needed for AC-coupling with metallic cable, and like the metallic cable system, present optical components are tolerant enough to withstand some variations in the average logic 1's density range.
Many well-known and well-characterized coding and decoding schemes have been developed and used for serial communication links that transport binary (2-level) signals. Some of the better known binary coding schemes are listed below, along with their respective advantages and disadvantages.
Source Code Restriction restricts the user at the source from injecting a data stream into the serial data link with a long sequence of logic 1's or logic 0's. This approach results in simple link hardware, but forces the user to modify the data stream in order to use the serial data link. These restrictions encourage some type of coding scheme to prevent long sequences of logic 1's or logic 0's.
Dedicated Timing Bit Usage requires the source circuitry to periodically insert, e.g. once every X transmitted bits, a bit to provide a bit transition. This approach results in relatively simple link hardware, but for large values of X, it does not guarantee a logic 1's density of approximately fifty percent. Furthermore, if X is made to be a small number of bits, then this approach results in low channel bandwidth utilization.
Bit Insertion requires the data stream to be modified so that a consecutive string of Y logic 0's (or Y logic 1's) results in the addition of a logic 1 bit (or logic 0 bit) to the data stream. This approach is relatively bandwidth efficient, but it leads to more complicated link hardware and also can modify the effective data rate at which the valuable data is being transmitted--i.e., the useful data rate is effectively reduced every time a bit is inserted into the stream.
Data Scrambling of Non-Return-to-Zero (NRZ) data uses a feedback circuit on the source circuitry to convert the user data stream into a new data stream which will ideally have many transitions in it. This approach is very bandwidth efficient, but it does not guarantee that the new encoded data stream on the communication link will have many bit transitions, because there are always input patterns that may be generated by the user that will produce a long string of logic 1's or logic 0's at the output of the scrambler circuit. During any such long sequence of logic 1's or logic 0's synchronization of a clock recovery circuit will be lost and with the loss of synchronization, a large increase in data errors. In addition, if the data stream is to be actively switched to different destinations (between two consecutive bits), then the feedback algorithms used for many scrambler circuits will not permit the receiver circuitry to easily recover the initial signal without knowledge of the preceding data that might have been routed elsewhere.
The Forced Bit Errors scheme simply over-writes the user data stream whenever too many logic 1's or logic 0's have passed through the communication link. In effect, the source circuitry merely inserts bit errors in the data stream. This approach results in simple hardware, but it also can lead to high bit error rates as seen by the end users. Higher level protocols are therefore required to detect the errors, and this can result in many re-transmissions of pieces of the data stream, which means inefficient bandwidth utilization.
Manchester Encoding guarantees at least one signal transition within every bit period. This transition will occur at the beginning of the bit period and/or in the middle of the bit period. For a logic 1 bit, the signal is held in the high state during the first half of the bit period and is held in the low state during the second half of the bit period. For a logic 0 bit, the signal is held in the low state during the first half of the bit period and is held in the high state during the second half of the bit period. This approach results in an ideal logic 1's density of exactly fifty percent, so the line is said to be "DC-balanced." However, because the pulses on the line can occupy shorter time intervals that are exactly half of the time intervals in a NRZ pulse, the channel bandwidth (and the frequency of the source and receiver circuitry) must be increased by a factor of two when compared with NRZ coding techniques.
mBnB Encoding, which is a generalization of 4B5B encoding method of Sperry Corporation, now part of UNISYS, in which each of the 16 possible 4 Bit binary data blocks was encoded into a corresponding 5 Bit binary data block for data communication. Generally, mBnB encoding takes blocks of m-bits of binary data from the user data stream and converts each m-bit block into a block of n-bits of binary data using a pre-specified mapping function. The known mBnB coding schemes use look-up tables in memory to perform the encoding and decoding. Look-up tables in memory, even in ROM, take time so an encoder or decoder using a direct look-up in a memory is bandwidth limited by the access time of the memory. The communications bandwidth efficiency resulting from the use of an mBnB encoding scheme is given by m/n, so the throughput data rate and the serial communication link rate must be increased by a factor of n/m when compared to the line rate of the user data stream. Three mBnB Encoding methods are known: 4B/5B; 5B/6B and 7B/8B. These known encoding and decoding methods are mentioned in Digital Telephony, Second Edition, by J. Bellamy on pages 394-398. A 5B/6B encoding scheme has been used for a 565 mega bit per second data link and a 7B/8B encoding scheme has been used for a 280 mega bit per second data link. The bandwidth efficiency for the 5B/6B scheme is 83 percent and for the 7B/8B scheme is 87.5 per cent. It is desirable that the bandwidth efficiency of a serial communication link be as high as possible without sacrificing synchronization of the recovered clock.
It is an object of the present invention to provide a method for encoding groups of m data bits, where each group contains at least eight bits, into groups of n bits, where n is greater than m, and each group of n bits into which an m bit group is encoded has a density of logic 1's sufficient for clock recovery and synchronization.
It is another object of the invention to provide an apparatus that encodes m bit data groups, where m is at least eight, into n bits, where n is greater than m, using higher speed techniques than direct look-up in a memory.